#include <string>
using namespace std;

void GetNext(const string &str, int next[])
{
    next[0] = -1;
    int k = -1; // 将k初始化为next[i-1]
    int i = 1;
    while (i < str.size())
    {
        if (k == -1 || str[i - 1] == str[k])
        {
            next[i] = k + 1;
            ++k;
            ++i;
        }
        else
        {
            k = next[k];
        }
    }
}

size_t Find_KMP(const string &str, const string &substr, size_t pos = 0)
{
    // 预处理模式串，得到对应的next数组
    int m = str.size();
    int n = substr.size();
    int next[n];
    GetNext(substr, next);

    // for (auto e : next)
    //   cout << e << " ";
    // cout << endl;

    // 利用next数组进行KMP模式匹配
    int i = pos, j = 0;
    while (i < m && j < n)
    {
        if (j == -1 || str[i] == substr[j])
        {
            ++j;
            ++i;
        }
        else
        {
            j = next[j];
        }
    }

    if (j == n)
        return i - n;
    else
        return -1;
}

size_t Find_BF(const string &str, const string &substr, size_t pos = 0)
{
    size_t m = str.size();
    size_t n = substr.size();
    for (size_t i = pos; i < m; ++i)
    {
        if (str[i] == substr[0])
        {
            size_t j = 1;
            while (j < n && str[i + j] == substr[j])
            {
                ++j;
            }
            if (j == n)
            {
                return i;
            }
        }
    }
    return -1;
}